﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//救命题
//1，归并
//2，快排
//3，二分查找

namespace CodeTop.复习九月份
{
    public class Solution912
    {
        public int[] SortArray(int[] nums)
        {
           
            int mid=nums.Length/2;

            int len=nums.Length;

            int[] res = MergeSort(nums,0,len-1);

            return res;    
        }

        private int[] MergeSort(int[] nums,int start,int end)
        {

            if (start < end)
            {
                int mid = (start + end) / 2;
                int[] resL = MergeSort(nums, start, mid);
                int[] resR = MergeSort(nums, mid + 1, end);


                return Partition(resL, resR);
            }
            {
                int[] res=new int[1];
                res[0] = nums[start];
                return res;

            }
           

          
        }

        private int[] Partition(int[] nums1, int[] nums2)
        {
            int len1 = nums1.Length;
            int len2= nums2.Length;
            int[] res=new int[len1+len2];
            int index = 0;
            int start1 = 0;
            int start2 = 0;
            int end1 = len1;
            int end2 = len2;

            while(start1 < end1&&start2<end2) {

                if (nums1[start1] <nums2[start2])
                {

                    res[index++] = nums1[start1];
                    start1++;
                }
                else
                {
                    res[index++] = nums2[start2];
                    start2++;
                }

            }
            if (start1 == end1) {

                while (start2 < end2)
                {
                    res[index++] = nums2[start2++];
                }


            }
            else
            {
                while (start1 < end1)
                {
                    res[index++] = nums1[start1++];
                }
            }
            return res;
           


        }
    }

    class ProgramSortMerge
    {
        static void Main912(string[] args)
        {

            // int[] nums = [110, 100, 0];
            int[] nums = [5, 2, 3, 1];

            Solution912 sol = new Solution912();
            int[] res = sol.SortArray(nums);
            for (int i = 0; i < res.Length; i++)
            {
                Console.Write(res[i] + ",");
            }
            Console.WriteLine();
        }


    }
}
